#ifndef __CDS_BTREE_H__
#define __CDS_BTREE_H__

#ifdef __cplusplus
extern "C" {
#endif
/**
 *
 */
//B树阶数
#define M 4 
#define MAX M-1
#define MIN ((M+1)/2-1)  

//M阶B树的结点关键字个数n的范围: [m/2]-1<=n<=M-1,  其中[m/2]表示m/2向上取整
// 例如:  4阶B树, 结点中关键字个数为: 1<=n<=3
//        5阶B树, 结点中关键字个数为: 2<=n<=4

//关键字封装
typedef struct keyword{
    unsigned long key;
    void * data;
} btree_keyword_t;

//B树节点封装
typedef struct btree_node{
    int num; //关键字数量
    int leaf; //叶子节点标志
    struct btree_node * parent; //双亲节点指针
    btree_keyword_t  keywords[M]; //关键字数组,一个M阶B数，每个节点最多M-1个关键字,但最后留一个空位置用于插入第四个关键字(之后会抽掉一个到父节点上去)
    struct btree_node *children[M+1]; //子节点指针数组
} btree_node_t;

//B树结构入口
typedef struct btree {
    struct btree_node * root; 
    int size;//数据量 
} btree_t;

typedef void (*travel_func_t)(unsigned long key, void * data);
typedef void (*destroy_func_t)(void * data);

#define BTREE_INIT( tree ) do{\
    tree->root = NULL;\
    tree->size = 0; \
}while(0)

//插入
void * btree_insert( btree_t * tree, unsigned long key, void * data );
//删除
void *  btree_del( btree_t * tree, unsigned long key ); 
//搜索
void *  btree_search( btree_t * tree, unsigned long key ); 
//中序遍历
void btree_travel_middle( btree_t * tree ,travel_func_t travel); 
//层次遍历
void btree_travel_level( btree_t * tree ,travel_func_t travel); 
//层次打印 
void btree_print_tree( btree_t * tree );
//清空
void btree_clear( btree_t * tree, destroy_func_t destroy ); 

#ifdef __cplusplus
}
#endif 

#endif // __CDS_BTREE_H__
